package com.xj.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉搜索树的最小绝对差
 */
public class L530_二叉搜索树的最小绝对差 {

    /**
     * 给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
     * <p>
     * 示例：
     * <p>
     * 输入：
     * <p>
     * 1
     * \
     * 3
     * /
     * 2
     * <p>
     * 输出：
     * 1
     * <p>
     * 解释：
     * 最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
     *  
     * <p>
     * 提示：
     * <p>
     * 树中至少有 2 个节点。
     * 本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(2);
        System.out.println(getMinimumDifference(root));

        System.out.println(getMinimumDifferenceGood(root));
    }

    //自己的解法：中序的第一个和最后一个节点，直接比大小。找最小值
    public static int getMinimumDifference(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int length = list.size();
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < length - 1; i++) {
            min = min > list.get(i + 1) - list.get(i) ? list.get(i + 1) - list.get(i) : min;
        }

        return min;
    }

    public static void inorder(TreeNode root, List list) {
        if (root == null) return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }

    //精彩解法：中序遍历+存储前一个节点
    static TreeNode pre = null;
    static int res = Integer.MAX_VALUE;
    public static int getMinimumDifferenceGood(TreeNode root) {
        inorderGood(root);
        return res;
    }

    //在递归时就把结果处理了
    public static void inorderGood(TreeNode root) {
        if(root == null) {
            return;
        }
        inorderGood(root.left);
        if(pre != null) {
            res = Math.min(res, root.val - pre.val);
        }
        pre = root;
        inorderGood(root.right);
    }

}
